class Solution:
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if len(word) > len(board)*len(board[0]):
            return False
        row = len(board)
        col = len(board[0])
        visited = [[False for j in range(col)] for i in range(row)]
        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0]:
                    if self.dfs(board, visited, word, 0, i, j):
                        return True
        return False

    def dfs(self, board, visited, word, index, x, y):
        if x < 0 or y < 0 or x == len(board) or y == len(board[0]) or board[x][y] != word[index]\
                or visited[x][y]:
            return False
        if index == len(word)-1:
            return True
        visited[x][y] = True
        res = self.dfs(board, visited, word, index+1, x+1, y) or self.dfs(board, visited, word, index+1, x-1, y)\
            or self.dfs(board, visited, word, index+1, x, y+1) or self.dfs(board, visited, word, index+1, x, y-1)
        visited[x][y] = False
        return res
